package com.tys.algorithm.advanced.code.class15;

/**
 * leetcode原题
 * https://leetcode.com/problems/friend-circles/
 * 可以直接通过
 * 省份数量
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。
 * 如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，
 * 那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 * 返回矩阵中 省份 的数量。
 */
public class Code01_FriendCircles {

    public static int findCircleNum(int[][] M) {
        int N = M.length;
        //初始化并查集
        // {0} {1} {2} {N-1}
        UnionFind unionFind = new UnionFind(N);
        //只遍历右上半区
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (M[i][j] == 1) { // i和j互相认识
                    //合并i集合和j集合
                    unionFind.union(i, j);
                }
            }
        }
        //返回并查集有几个集合
        return unionFind.sets();
    }

    public static class UnionFind {
        // parent[i] = k ： i的父亲是k
        private int[] parent;
        // size[i] = k ： 如果i是代表节点，size[i]才有意义，否则无意义
        // i所在的集合大小是多少
        private int[] size;
        // 辅助结构：做路径压缩代替栈
        private int[] help;
        // 一共有多少个集合
        private int sets;

        public UnionFind(int N) {
            parent = new int[N];
            size = new int[N];
            help = new int[N];
            sets = N; //初始集合个数N
            for (int i = 0; i < N; i++) {
                parent[i] = i; //指向自己
                size[i] = 1; //大小1
            }
        }

        // 从i开始一直往上，往上到不能再往上，代表节点，返回
        // 这个过程要做路径压缩
        private int find(int i) {
            //help数组的指针
            int hi = 0;
            //i指向自己时就是代表节点，退出循环
            while (i != parent[i]) {
                //沿途所有位置，放入help数组
                help[hi++] = i;
                //找i的父节点
                i = parent[i];
            }
            //扁平化，将路径压缩
            for (hi--; hi >= 0; hi--) {
                //重新设置help中节点的父节点
                parent[help[hi]] = i;
            }
            //返回代表节点
            return i;
        }

        //合并
        public void union(int i, int j) {
            //找到i的代表节点
            int f1 = find(i);
            //找到j的代表节点
            int f2 = find(j);
            //不是同一个集合就合并
            if (f1 != f2) {
                //小挂大
                if (size[f1] >= size[f2]) {
                    //f1是大集合，f2小集合
                    //更新大的集合大小
                    size[f1] += size[f2];
                    //小集合父亲指向大集合的代表节点
                    parent[f2] = f1;
                } else {
                    //f2是大集合，f1小集合
                    //更新大的集合大小
                    size[f2] += size[f1];
                    //小集合父亲指向大集合的代表节点
                    parent[f1] = f2;
                }
                //合并后集合总数减1
                sets--;
            }
        }

        //返回集合个数
        public int sets() {
            return sets;
        }
    }

}
